package dome1;


import java.util.*;



public class Text {
    public TreeNode Convert(TreeNode pRootOfTree) {
        TreeNode root = pRootOfTree;
        Queue<TreeNode> queue = new LinkedList<>();
        queue = inorderTraversal(root);
        root = queue.poll();
        TreeNode prev = root;
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            prev.right = cur;
            cur.left = prev;
            prev = cur;
        }
        return root;
    }

    public Queue<TreeNode> inorderTraversal(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return null;
        TreeNode cur = root;
        while(cur!=null || !stack.empty()) {
            while(cur!=null) {
               stack.push(cur);
               cur = cur.left;
            }
            cur = stack.pop();
            queue.offer(cur);
            cur = cur.right;
        }
        return queue;
    }
}

class Solution {
    //返回的第一个指针，即为最小值，先定为null
    public TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定为null
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            //中序递归，叶子为空则返回
            return null;
        //首先递归到最左最小值
        Convert(pRootOfTree.left);
        //找到最小值，初始化head与pre
        if(pre == null){
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        //当前节点与上一节点建立连接，将pre设置为当前值
        else{
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}

